////////////////////////////////////////////////////////////////////////////
//
//  CryEngine Source File.
//  Copyright (C), Crytek, 2001-2007.
// -------------------------------------------------------------------------
//  File name:   RenderMeshUtils.cpp
//  Created:     14/11/2006 by Timur.
//  Description: 
// -------------------------------------------------------------------------
//  History:
//
////////////////////////////////////////////////////////////////////////////

#include "StdAfx.h"
#include "RenderMeshUtils.h"






namespace
{
	enum { MAX_CACHED_HITS = 8 };
	struct SCachedHit
	{
		IRenderMesh *pRenderMesh;
		SRayHitInfo hitInfo;
		Vec3 tri[3];
	};
	static SCachedHit last_hits[MAX_CACHED_HITS];


	struct SIndicePreloader
	{	
		enum { INDICES_BUFFER_SIZE = 4096 };		
		enum { DMA_ID = 3 };

		// cppcheck-suppress uninitVar
		SIndicePreloader( uint16 *pInds, uint32 nFirstIndice, uint32 nNumIndices ) :
			m_pIndices(pInds), 			
			m_nNumIndices(nFirstIndice+nNumIndices), 
			pFetchBuffer( (char*)&m_pBuffer[0]), 
			pUseBuffer( (char*)&m_pBuffer[1]),
			m_nNextPreLoadIndex(nFirstIndice),
			m_nMaxAvaibleIndex(0),
			m_nUseBufferOffset(0),
			m_nFetchBufferOffset(0),
			m_nSpuOffsetFetch(0),
			m_nSpuOffsetUse(0),
			m_lastBufferAccess(NULL)
			{
				// do the first downtransfer sync, after it do it async
				// and start the next one as soon as we need a non-prefetches indice
				StartIndiceTransfer();				
			}

			~SIndicePreloader()
			{
				SyncFetchBuffer();
			}

			uint16 GetIndice( uint32 nIndex )
			{
#if defined(PREFETCH_INDICES)				
				uint16 *pInds = reinterpret_cast<uint16*>( &pUseBuffer[m_nUseBufferOffset] - m_nSpuOffsetUse);
				m_lastBufferAccess = &pInds[nIndex];								
				return pInds[nIndex];
#else
				return m_pIndices[nIndex];
#endif
			}
			
			bool IsPreLoaded( uint32 nIndex )
			{
#if defined(PREFETCH_INDICES)				
				return nIndex < m_nMaxAvaibleIndex;
#else
				return true;
#endif
			}
			
			void SwitchBuffers()
			{
#if defined(PREFETCH_INDICES)
				SyncFetchBuffer();
				SwapBuffers();
				StartIndiceTransfer();
#endif
			}
	private:		
		void SyncFetchBuffer() 
		{			
#if defined(PREFETCH_INDICES)		
			memtransfer_sync(DMA_ID);
#endif
		}

		void SwapBuffers()
		{			
#if defined(PREFETCH_INDICES)
			std::swap(pUseBuffer, pFetchBuffer);
			std::swap(m_nUseBufferOffset,m_nFetchBufferOffset);	
			std::swap(m_nSpuOffsetFetch,m_nSpuOffsetUse);
			m_nMaxAvaibleIndex = m_nNextPreLoadIndex;
#endif
		}

		void StartIndiceTransfer()
		{
#if defined(PREFETCH_INDICES)		
			// get src ptr and align it to 128 bytes
			uint32 nSrcPtr = (uint32)&m_pIndices[m_nNextPreLoadIndex];
			m_nFetchBufferOffset = nSrcPtr & 127;
			nSrcPtr &= ~127;
			m_nSpuOffsetFetch = (uint32)((char*)&m_pIndices[m_nNextPreLoadIndex] - (char*)&m_pIndices[0]);
		
			// adjust max buffer size to take pre bytes into account
			uint32 nMaxBuffer = INDICES_BUFFER_SIZE - (m_nFetchBufferOffset !=0 ? 128 : 0);

			// compute size of remaining indices in bytes
			uint32 nRemainingIndices = (m_nNumIndices - m_nNextPreLoadIndex);
			
			// preload either a full buffer or the remaining indices(use the smaller value)		
			uint32 nSize = min( nMaxBuffer, nRemainingIndices *sizeof(uint16) );

			if( nSize == 0 )
				return;
			
			
			// adjust next preload index(curIndex plus elements in size plus 1 to get to the next index
			m_nNextPreLoadIndex += nSize/sizeof(uint16);
			m_nNextPreLoadIndex -= (m_nNextPreLoadIndex%3); // clamp preloaded indices to a multiple of three
			
			// adjust size(keep in mind: pre bytes due to alignment and align the final size)
			nSize += m_nFetchBufferOffset;
			nSize = (nSize+127) & ~127;

			memtransfer_from_main(pFetchBuffer, SPU_MAIN_PTR( (void*)nSrcPtr), nSize, DMA_ID );
#endif
		}

		char m_pBuffer[2][INDICES_BUFFER_SIZE] _ALIGN(128);
		SPU_DOMAIN_LOCAL char *pUseBuffer;
		SPU_DOMAIN_LOCAL char *pFetchBuffer;

		uint32 m_nUseBufferOffset;
		uint32 m_nFetchBufferOffset;
		SPU_DOMAIN_MAIN uint16 *m_pIndices;
		uint32 m_nNumIndices;
		uint32 m_nNextPreLoadIndex;	
		uint32 m_nMaxAvaibleIndex;
		uint32 m_nSpuOffsetFetch;
		uint32 m_nSpuOffsetUse;
		void *m_lastBufferAccess;
	};
	

	//idea: 
	//	index buffer is transferred unconditionally
	//	transfer size is multiple cachelines (to account for dma start latencies)
	//	before accessing the vertices, first prefetch them
	//	each prefetch checks if cache line covering entire vertex exists, if so: corresponding lru is increased
	//	if not, the lowest lru line is replaced and lru is updated
	struct SVtxCache
	{
		enum { PREF_VTX_NUM = 8 };//do not change, loop unrolling fixed
#ifdef USE_VTX_CACHE
		enum { PREF_VTX_TRANSFER_SIZE = 1024 };
		uint8 buf[PREF_VTX_TRANSFER_SIZE*PREF_VTX_NUM] _ALIGN(128);//buffer to transfer into
		uint32 addrStart[PREF_VTX_NUM];		//current start addresses
		uint32 addrEnd[PREF_VTX_NUM];			//current end addresses
		int lru[PREF_VTX_NUM];						//LRU of address cache
		int curLru;												//current LRU
		int lastSyncdLru;									//lru last dma finished to not replace transfers inflight
		uint32 dmaStarted;							
		ILINE SVtxCache(){memset(this, 0, sizeof(*this));for(uint32 i=0;i<PREF_VTX_NUM;++i)lru[i]=-1;}
		ILINE uint32 LowestLRUIdx()const
		{
			uint32 lowestIdx = 0;		
			int lowestLru = lru[0];	int lru1 = lru[1];			int lru2 = lru[2];			int lru3 = lru[3];			
			int lru4 = lru[4];			int lru5 = lru[5];			int lru6 = lru[6];			int lru7 = lru[7];
			lowestIdx = (lru1 < lowestLru)?1:lowestIdx;					lowestLru = (lru1 < lowestLru)?lru1:lowestLru;			
			lowestIdx = (lru2 < lowestLru)?2:lowestIdx;					lowestLru = (lru2 < lowestLru)?lru2:lowestLru;			
			lowestIdx = (lru3 < lowestLru)?3:lowestIdx;					lowestLru = (lru3 < lowestLru)?lru3:lowestLru;
			lowestIdx = (lru4 < lowestLru)?4:lowestIdx;					lowestLru = (lru4 < lowestLru)?lru4:lowestLru;
			lowestIdx = (lru5 < lowestLru)?5:lowestIdx;					lowestLru = (lru5 < lowestLru)?lru5:lowestLru;
			lowestIdx = (lru6 < lowestLru)?6:lowestIdx;					lowestLru = (lru6 < lowestLru)?lru6:lowestLru;
			lowestIdx = (lru7 < lowestLru)?7:lowestIdx;					lowestLru = (lru7 < lowestLru)?lru7:lowestLru;
			return lowestIdx;
		}
		ILINE int FindAddr(uint32 startAddr, uint32 endAddr)const
		{
			uint32 addrStart0 = addrStart[0];				uint32 addrEnd0 = addrEnd[0];
			uint32 addrStart1 = addrStart[1];				uint32 addrEnd1 = addrEnd[1];
			uint32 addrStart2 = addrStart[2];				uint32 addrEnd2 = addrEnd[2];
			uint32 addrStart3 = addrStart[3];				uint32 addrEnd3 = addrEnd[3];
			uint32 addrStart4 = addrStart[4];				uint32 addrEnd4 = addrEnd[4];
			uint32 addrStart5 = addrStart[5];				uint32 addrEnd5 = addrEnd[5];
			uint32 addrStart6 = addrStart[6];				uint32 addrEnd6 = addrEnd[6];
			uint32 addrStart7 = addrStart[7];				uint32 addrEnd7 = addrEnd[7];
			IF(startAddr >= addrStart0 && endAddr <= addrEnd0,0)return 0;
			IF(startAddr >= addrStart1 && endAddr <= addrEnd1,0)return 1;
			IF(startAddr >= addrStart2 && endAddr <= addrEnd2,0)return 2;
			IF(startAddr >= addrStart3 && endAddr <= addrEnd3,0)return 3;
			IF(startAddr >= addrStart4 && endAddr <= addrEnd4,0)return 4;
			IF(startAddr >= addrStart5 && endAddr <= addrEnd5,0)return 5;
			IF(startAddr >= addrStart6 && endAddr <= addrEnd6,0)return 6;
			IF(startAddr >= addrStart7 && endAddr <= addrEnd7,0)return 7;
			return -1;
		}
#endif
		ILINE void Sync()
		{
#ifdef USE_VTX_CACHE
			if(dmaStarted)
				memtransfer_sync(0);
			dmaStarted = false;
			lastSyncdLru = curLru;
#endif
		}
		ILINE bool Pref(void* p, uint32 s)
		{
#ifdef USE_VTX_CACHE
			uint32 startAddr	= (uint32)p & ~127;
			uint32 endAddr		= (uint32)p + s;
			//check if already present, if so, add curLru
			int entryIdx = FindAddr(startAddr, endAddr);
			if(entryIdx == -1)
			{
				entryIdx = LowestLRUIdx();
				IF(lru[entryIdx] >= lastSyncdLru, 0)return false;//max capacity reached
				addrStart[entryIdx]			= startAddr;
				uint32 transferEndAddr	= startAddr + PREF_VTX_TRANSFER_SIZE;
				//special care needs to be taken if transfer crosses 64KB range as it might get out of physically mapped range
				const uint32 physPageMask		= ~(64*1024-1);
				const uint32 physPageStart	= startAddr & physPageMask;
				IF(physPageStart != (transferEndAddr & physPageMask) && 
					physPageStart == (endAddr & physPageMask),0)
					transferEndAddr = transferEndAddr & physPageMask;
				addrEnd[entryIdx]		= transferEndAddr;
				void *pStart = SPU_MAIN_PTR((void*)startAddr);
				memtransfer_from_main(&buf[entryIdx * PREF_VTX_TRANSFER_SIZE], pStart, transferEndAddr - startAddr, 0);
				dmaStarted = true;
			}
			lru[entryIdx] = curLru++;
			return true;
#endif
		}
		ILINE const void* Vtx(void* p, uint32 s)const
		{
#ifdef USE_VTX_CACHE
			int index = FindAddr((uint32)p, (uint32)p + s);
			IF(index == -1,0)	snPause();
			return (void*)&buf[index * PREF_VTX_TRANSFER_SIZE + (uint32)p - addrStart[index]];
#else
			return p;
#endif
		}
	};
}

bool SIntersectionData::Init(IRenderMesh *param_pRenderMesh, SRayHitInfo *param_pHitInfo, IMaterial *param_pMtl, bool param_bRequestDecalPlacementTest)
{
	pRenderMesh = param_pRenderMesh;
	pHitInfo = param_pHitInfo;
	pMtl = param_pMtl;
	bDecalPlacementTestRequested = param_bRequestDecalPlacementTest;

	bool bAllDMeshData = pHitInfo->bGetVertColorAndTC;

	nVerts =  pRenderMesh->GetVerticesCount();
	nInds =  pRenderMesh->GetIndicesCount();

	if (nInds == 0 || nVerts == 0)
		return false;
	pPos =	(uint8*)pRenderMesh->GetPosPtr(nPosStride, FSL_READ);
	pInds = pRenderMesh->GetIndexPtr(FSL_READ);

	if(!pPos || !pInds)
	{
		pRenderMesh->UnLockForThreadAccess();
		return false;
	}

	if( bAllDMeshData )
	{
		pUV	=	(uint8*)pRenderMesh->GetUVPtr(nUVStride, FSL_READ);
		pCol = (uint8*)pRenderMesh->GetColorPtr(nColStride, FSL_READ);

		pTang = pRenderMesh->GetTangentPtr(nTangStride, FSL_READ);
		pBNorm = pRenderMesh->GetBinormalPtr(nBNormStride, FSL_READ);
	}	

	return true;
}

template <class T> bool GetBarycentricCoordinates(T P_A, T B_A, T C_A, float & u, float & v, float & w, float fBorder)
{
  // Compute vectors        
  const T & v0 = C_A;
  const T & v1 = B_A;
  const T & v2 = P_A;

  // Compute dot products
  float dot00 = v0.Dot(v0);
  float dot01 = v0.Dot(v1);
  float dot02 = v0.Dot(v2);
  float dot11 = v1.Dot(v1);
  float dot12 = v1.Dot(v2);

  // Compute barycentric coordinates
  float invDenom = 1.f / (dot00 * dot11 - dot01 * dot01);
  u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  v = (dot00 * dot12 - dot01 * dot02) * invDenom;
  w = 1.f - u - v;

  // Check if point is in triangle
  return (u >= -fBorder) && (v >= -fBorder) && (w >= -fBorder);
}

void CRenderMeshUtils::ClearHitCache()
{
  // do not allow items to stay too long in the cache, it allows to minimize wrong hit detections
  memmove( &last_hits[1],&last_hits[0],sizeof(last_hits)-sizeof(last_hits[0]) ); // Move hits to the end of array, throwing out the last one.
  memset(&last_hits[0], 0, sizeof(last_hits[0]));
}
//////////////////////////////////////////////////////////////////////////
#if !defined(__SPU__)
bool CRenderMeshUtils::RayIntersection( IRenderMesh *pRenderMesh, SRayHitInfo &hitInfo,IMaterial *pMtl)
{
	SIntersectionData data;
	
	pRenderMesh->LockForThreadAccess();
	if( !data.Init(pRenderMesh, &hitInfo, pMtl) )
	{
		return false;		
	}
	
	// forward call to implementation
	bool result = CRenderMeshUtils::RayIntersectionImpl(&data,&hitInfo, pMtl, false );

	pRenderMesh->UnlockStream(VSF_GENERAL);
	pRenderMesh->UnlockIndexStream();
	pRenderMesh->UnLockForThreadAccess(); 
	return result;
}
#endif

SPU_ENTRY(RayIntersection)
void CRenderMeshUtils::RayIntersectionAsync( SIntersectionData *pIntersectionRMData )
{		
	// forward call to implementation

	// use stack variants of hitInfo and Intersection RenderMesh data
	SpuStackValue<SRayHitInfo, true, true > stackHitInfo( *pIntersectionRMData->pHitInfo );
	SpuStackValue<SIntersectionData, true, true> stackIntersectionRMData( *pIntersectionRMData );

	SRayHitInfo &rHitInfo = stackHitInfo;
	SIntersectionData &rIntersectionData = stackIntersectionRMData;

	if(CRenderMeshUtils::RayIntersectionImpl( &rIntersectionData, &rHitInfo, rIntersectionData.pMtl, true ))
	{
		if(rIntersectionData.bDecalPlacementTestRequested && GetFloatCVar(e_DecalsPlacementTestAreaSize))
		{		
			rIntersectionData.fDecalPlacementTestMaxSize = 0.f;

			for(float fRange = GetFloatCVar(e_DecalsPlacementTestAreaSize)*.5f; fRange <= GetFloatCVar(e_DecalsPlacementTestAreaSize); fRange *= 2.f)
			{
				Vec3 vDir = -rHitInfo.vHitNormal;
				vDir.Normalize();

				Vec3 vRight;
				Vec3 vUp;

				if(fabs(vDir.Dot(Vec3(0,0,1))) > 0.995f)
				{
					vRight = Vec3(1,0,0);
					vUp = Vec3(0,1,0);
				}
				else
				{
					vRight = vDir.Cross(Vec3(0,0,1));
					vUp = vRight.Cross(vDir);
				}

				Vec3 arrOffset[4] = { vRight*fRange, -vRight*fRange, vUp*fRange, -vUp*fRange };

				SRayHitInfo hInfo;
				SIntersectionData intersectionData;

				float fDepth = fRange*0.2f;

				int nPoint;
				for(nPoint=0; nPoint<4; nPoint++)
				{
					intersectionData = rIntersectionData;

					hInfo = rHitInfo;
					hInfo.inReferencePoint = hInfo.vHitPos + arrOffset[nPoint];//*fRange;
					hInfo.inRay.origin = hInfo.inReferencePoint + hInfo.vHitNormal*fDepth;
					hInfo.inRay.direction = -hInfo.vHitNormal*fDepth*2.f;
					hInfo.fMaxHitDistance = fDepth;
					if(!CRenderMeshUtils::RayIntersectionImpl(&intersectionData, &hInfo, rIntersectionData.pMtl, true))
						break;
				}

				if(nPoint==4)
					rIntersectionData.fDecalPlacementTestMaxSize = fRange;
				else
					break;
			}
		}
	}
}

bool CRenderMeshUtils::RayIntersectionImpl( SIntersectionData *pIntersectionRMData, SRayHitInfo *phitInfo, IMaterial *pMtl, bool bAsync )
{
#if !defined(__SPU__)  // currently Async(SPU) RayIntersections are only used by physics mesh collision, and there this flag is never set
  IF((!phitInfo->bNoFastIntersect && phitInfo->bGetVertColorAndTC),0)
    return RayIntersectionFastImpl( *pIntersectionRMData, *phitInfo, pMtl, bAsync );
#endif

	SIntersectionData &rIntersectionRMData = *pIntersectionRMData;
	SRayHitInfo &hitInfo = *phitInfo;

	SVtxCache vtxCache;	

  FUNCTION_PROFILER_3DENGINE;

	//CTimeValue t0 = gEnv->pTimer->GetAsyncTime();

	float fMaxDist2 = hitInfo.fMaxHitDistance*hitInfo.fMaxHitDistance;

	Vec3 vHitPos(0,0,0);
	Vec3 vHitNormal(0,0,0);

#if !defined(__SPU__)
	static bool bClearHitCache = true;
	if (bClearHitCache && !bAsync)
	{
		memset( last_hits,0,sizeof(last_hits) );
		bClearHitCache = false;
	}

	if (hitInfo.bUseCache && !bAsync)
	{
		Vec3 vOut;
		// Check for cached hits.
		for (int i = 0; i < MAX_CACHED_HITS; i++)
		{
			if (last_hits[i].pRenderMesh == rIntersectionRMData.pRenderMesh)
			{
				// If testing same render mesh, check if we hit the same triangle again.
				if (Intersect::Ray_Triangle( hitInfo.inRay,last_hits[i].tri[0], last_hits[i].tri[2], last_hits[i].tri[1],vOut ))
				{
					if (fMaxDist2)
					{
						float fDistance2 = hitInfo.inReferencePoint.GetSquaredDistance(vOut);
						if (fDistance2 > fMaxDist2)
							continue; // Ignore hits that are too far.
					}

					// Cached hit.
					hitInfo.vHitPos = vOut;
					hitInfo.vHitNormal = last_hits[i].hitInfo.vHitNormal;
					hitInfo.nHitMatID = last_hits[i].hitInfo.nHitMatID;
					hitInfo.nHitSurfaceID = last_hits[i].hitInfo.nHitSurfaceID;

					if(hitInfo.inRetTriangle)
					{
						hitInfo.vTri0 = last_hits[i].tri[0];
						hitInfo.vTri1 = last_hits[i].tri[1];
						hitInfo.vTri2 = last_hits[i].tri[2];
					}
					//CTimeValue t1 = gEnv->pTimer->GetAsyncTime();
					//CryLogAlways( "TestTime :%.2f", (t1-t0).GetMilliSeconds() );
					//static int nCount = 0; CryLogAlways( "Cached Hit %d",++nCount );
          hitInfo.pRenderMesh = rIntersectionRMData.pRenderMesh;
					rIntersectionRMData.bResult = true;
					return true;
				}
			}
		}
	}

	int nUVStride = rIntersectionRMData.nUVStride;
	uint8* pUV = NULL;

	int nColStride = rIntersectionRMData.nColStride;
	uint8* pCol = NULL;

	if (hitInfo.bGetVertColorAndTC)
	{
		pUV = rIntersectionRMData.pUV;
		pCol = rIntersectionRMData.pCol;
	}
#endif//__SPU__

	int nVerts = rIntersectionRMData.nVerts;
	int nInds = rIntersectionRMData.nInds;

	assert(nInds != 0 && nVerts != 0 );
	
	// get position offset and stride
	const int nPosStride = rIntersectionRMData.nPosStride;
	uint8* const pPos = rIntersectionRMData.pPos;

	// get indices
	uint16 *const pInds = rIntersectionRMData.pInds;

	assert(pInds != NULL && pPos != NULL );
	assert(nInds%3 == 0);

	float fMinDistance2 = FLT_MAX;

	Ray inRay = hitInfo.inRay;

	bool bAnyHit = false;

	Vec3 vOut;
	Vec3 tri[3];
	int nTriIndex = -1;

	// test tris
	PodArray<CRenderChunk>&	RESTRICT_REFERENCE Chunks = rIntersectionRMData.pRenderMesh->GetChunks();
	int nChunkCount = Chunks.Count();
	
	for(int nChunkId = 0; nChunkId < nChunkCount; nChunkId++)
	{
		SpuStackValue<CRenderChunk, false, true> pChunk( Chunks[nChunkId] );
		
		IF(pChunk->m_nMatFlags & MTL_FLAG_NODRAW || !pChunk->pRE,0)
			continue;
		const int16 nChunkMatID = pChunk->m_nMatID;

		bool b2Sided = false;

    if (pMtl)
		{
			const SShaderItem &shaderItem = pMtl->GetShaderItem(nChunkMatID);
			if (hitInfo.bOnlyZWrite && !shaderItem.IsZWrite())
			  continue;
			if (!shaderItem.m_pShader || shaderItem.m_pShader->GetFlags() & EF_NODRAW || shaderItem.m_pShader->GetFlags() & EF_DECAL)
				continue;
			if (shaderItem.m_pShader->GetCull() & eCULL_None)
				b2Sided = true;
      if(shaderItem.m_pShaderResources && shaderItem.m_pShaderResources->GetResFlags() & MTL_FLAG_2SIDED) 
        b2Sided = true;
		}
		
    int nLastIndexId = pChunk->nFirstIndexId + pChunk->nNumIndices;
		SIndicePreloader indicePreloader( rIntersectionRMData.pInds, pChunk->nFirstIndexId, pChunk->nNumIndices);

    IF(nLastIndexId-1 >= nInds,0)
    {
#if !defined(__SPU__)
      Error("%s (%s): invalid mesh chunk", __FUNCTION__, rIntersectionRMData.pRenderMesh->GetSourceName());
#endif
			rIntersectionRMData.bResult = false;		
      return 0;
    }
				
		// make line triangle intersection
		int i = pChunk->nFirstIndexId;
		indicePreloader.SwitchBuffers();
		while(i < nLastIndexId)
		{
#ifdef USE_VTX_CACHE
			int p = i;

			// switch buffers if we ran out of indices
			if( !indicePreloader.IsPreLoaded(p) )
				indicePreloader.SwitchBuffers();

			// prefetch all values possible
			while (	p < nLastIndexId && 
								indicePreloader.IsPreLoaded(p) &&
								vtxCache.Pref(&pPos[nPosStride* indicePreloader.GetIndice(p) ], sizeof(Vec3))
								)
			{
				++p;
			}
			IF(p==i,0)snPause();
			p -= (p-i)%3;//clamp p on multiple of 3
			vtxCache.Sync();
#else
			int p = nLastIndexId;
#endif
			for(;i < p; i += 3)//process all prefetched vertices
			{
				assert(indicePreloader.GetIndice(i+0)<nVerts);
				assert(indicePreloader.GetIndice(i+1)<nVerts);
				assert(indicePreloader.GetIndice(i+2)<nVerts);

				IF(pInds[i+2] >= nVerts,0)
				{
#if !defined(__SPU__)
					Error("%s (%s): invalid mesh indices", __FUNCTION__, rIntersectionRMData.pRenderMesh->GetSourceName());
#endif
					rIntersectionRMData.bResult = false;
					return 0;
				}

				// get tri vertices
				const Vec3& tv0 = (*(const Vec3*)vtxCache.Vtx(&pPos[nPosStride*indicePreloader.GetIndice(i+0)], sizeof(Vec3)));
				const Vec3& tv1 = (*(const Vec3*)vtxCache.Vtx(&pPos[nPosStride*indicePreloader.GetIndice(i+1)], sizeof(Vec3)));
				const Vec3& tv2 = (*(const Vec3*)vtxCache.Vtx(&pPos[nPosStride*indicePreloader.GetIndice(i+2)], sizeof(Vec3)));
				
				if (Intersect::Ray_Triangle( inRay,tv0, tv2, tv1,vOut ))
				{
					float fDistance2 = hitInfo.inReferencePoint.GetSquaredDistance(vOut);
					if (fMaxDist2)
					{
						if (fDistance2 > fMaxDist2)
							continue; // Ignore hits that are too far.
					}
					bAnyHit = true;
					// Test front.
					if (hitInfo.bInFirstHit)
					{
						vHitPos = vOut;
						hitInfo.nHitMatID = nChunkMatID;
						tri[0] = tv0; tri[1] = tv1; tri[2] = tv2;
						goto AnyHit;//need to break chunk loops, vertex loop and prefetched loop
					}
					if (fDistance2 < fMinDistance2)
					{
						fMinDistance2 = fDistance2;
						vHitPos = vOut;
						hitInfo.nHitMatID = nChunkMatID;
						tri[0] = tv0; tri[1] = tv1; tri[2] = tv2;
						nTriIndex = i;
					}
				}
				else 
				if(b2Sided)
				{
					if (Intersect::Ray_Triangle( inRay,tv0, tv1, tv2,vOut ))
					{
						float fDistance2 = hitInfo.inReferencePoint.GetSquaredDistance(vOut);
						if (fMaxDist2)
						{
							if (fDistance2 > fMaxDist2)
								continue; // Ignore hits that are too far.
						}

						bAnyHit = true;
						// Test back.
						if (hitInfo.bInFirstHit)
						{
							vHitPos = vOut;
							hitInfo.nHitMatID = nChunkMatID;
							tri[0] = tv0; tri[1] = tv2; tri[2] = tv1;
							goto AnyHit;//need to break chunk loops, vertex loop and prefetched loop
						}
						if (fDistance2 < fMinDistance2)
						{
							fMinDistance2 = fDistance2;
							vHitPos = vOut;
							hitInfo.nHitMatID = nChunkMatID;
							tri[0] = tv0; tri[1] = tv2; tri[2] = tv1;
							nTriIndex = i;
						}
					}
				}
			}
		}
	}
AnyHit:
	if (bAnyHit)
	{ 
    hitInfo.pRenderMesh = rIntersectionRMData.pRenderMesh;

		// return closest to the shooter
		hitInfo.fDistance = (float)cry_sqrtf(fMinDistance2);
		hitInfo.vHitNormal = (tri[1]-tri[0]).Cross(tri[2]-tri[0]).GetNormalized();
		hitInfo.vHitPos = vHitPos;
		hitInfo.nHitSurfaceID = 0; 
		
		if(hitInfo.inRetTriangle)
		{
			hitInfo.vTri0 = tri[0];
			hitInfo.vTri1 = tri[1];
			hitInfo.vTri2 = tri[2];
		}

#if !defined(__SPU__)
		if(hitInfo.bGetVertColorAndTC)
		{
			float u=0, v=0, w=0;
			if(GetBarycentricCoordinates(vHitPos-tri[0], tri[1]-tri[0], tri[2]-tri[0], u, v, w, 16.0f))
			{
				float arrVertWeight[3] = { max(0.f,w), max(0.f,v), max(0.f,u) };
				float fDiv = 1.f/(arrVertWeight[0]+arrVertWeight[1]+arrVertWeight[2]);
				arrVertWeight[0]*=fDiv;
				arrVertWeight[1]*=fDiv;
				arrVertWeight[2]*=fDiv;

				Vec2 tc0 = ((Vec2f16*)&pUV[nUVStride*pInds[nTriIndex+0]])->ToVec2();
				Vec2 tc1 = ((Vec2f16*)&pUV[nUVStride*pInds[nTriIndex+1]])->ToVec2();
				Vec2 tc2 = ((Vec2f16*)&pUV[nUVStride*pInds[nTriIndex+2]])->ToVec2();

				hitInfo.vHitTC = tc0*arrVertWeight[0] + tc1*arrVertWeight[1] + tc2*arrVertWeight[2];

				Vec4 c0 = (*(ColorB*)&pCol[nColStride*pInds[nTriIndex+0]]).toVec4();
				Vec4 c1 = (*(ColorB*)&pCol[nColStride*pInds[nTriIndex+1]]).toVec4();
				Vec4 c2 = (*(ColorB*)&pCol[nColStride*pInds[nTriIndex+2]]).toVec4();

				hitInfo.vHitColor = (c0*arrVertWeight[0] + c1*arrVertWeight[1] + c2*arrVertWeight[2]) / 255.f;
			}
		}
#endif

		if (pMtl)
		{
			pMtl = pMtl->GetSafeSubMtl(hitInfo.nHitMatID);
			if (pMtl)
				hitInfo.nHitSurfaceID = pMtl->GetSurfaceTypeId();
		}

#if !defined(__SPU__)
		if( !bAsync )
		{		
			//////////////////////////////////////////////////////////////////////////
			// Add to cached results.
			memmove( &last_hits[1],&last_hits[0],sizeof(last_hits)-sizeof(last_hits[0]) ); // Move hits to the end of array, throwing out the last one.
			last_hits[0].pRenderMesh = rIntersectionRMData.pRenderMesh;
			last_hits[0].hitInfo = hitInfo;
			memcpy( last_hits[0].tri,tri,sizeof(tri) );
			//////////////////////////////////////////////////////////////////////////
		}
#endif
	}
	//CTimeValue t1 = gEnv->pTimer->GetAsyncTime();
	//CryLogAlways( "TestTime :%.2f", (t1-t0).GetMilliSeconds() );

	rIntersectionRMData.bResult = bAnyHit;	
	return bAnyHit;
}

bool CRenderMeshUtils::RayIntersectionFast( IRenderMesh *pRenderMesh, SRayHitInfo &hitInfo,IMaterial *pMtl )
{
	SIntersectionData data;

	if( !data.Init(pRenderMesh, &hitInfo, pMtl) )
	{
		return false;		
	}

	// forward call to implementation
	return CRenderMeshUtils::RayIntersectionFastImpl(data,hitInfo, pMtl, false );
}

//////////////////////////////////////////////////////////////////////////
bool CRenderMeshUtils::RayIntersectionFastImpl( SIntersectionData &rIntersectionRMData, SRayHitInfo &hitInfo, IMaterial *pMtl, bool bAsync )
{
  float fBestDist = hitInfo.fMaxHitDistance; // squared distance works different for values less and more than 1.f

  Vec3 vHitPos(0,0,0);
  Vec3 vHitNormal(0,0,0);

  int nVerts = rIntersectionRMData.nVerts;
  int nInds = rIntersectionRMData.nInds;

	assert(nInds != 0 && nVerts != 0);
  
  // get position offset and stride
  int nPosStride = rIntersectionRMData.nPosStride;
  uint8* pPos = rIntersectionRMData.pPos;

  int nUVStride = rIntersectionRMData.nUVStride;
  uint8* pUV = rIntersectionRMData.pUV;

  int nColStride = rIntersectionRMData.nColStride;
  uint8* pCol = rIntersectionRMData.pCol;

  // get indices
  uint16 *pInds = rIntersectionRMData.pInds;

	assert(pInds != NULL && pPos != NULL);

  assert(nInds%3 == 0);

  Ray inRay = hitInfo.inRay;

  bool bAnyHit = false;

  Vec3 vOut;
  Vec3 tri[3];

  // test tris

	Line inLine(inRay.origin, inRay.direction);

	if(hitInfo.nHitTriID >= 0)
	{
    if(hitInfo.nHitTriID+2 >= nInds)
      return false;

		int I0 = pInds[hitInfo.nHitTriID+0];
		int I1 = pInds[hitInfo.nHitTriID+1];
		int I2 = pInds[hitInfo.nHitTriID+2];

    if(I0<nVerts && I1<nVerts && I2<nVerts)
    {
      // get tri vertices
      Vec3 & tv0 = *((Vec3*)&pPos[nPosStride*I0]);
      Vec3 & tv1 = *((Vec3*)&pPos[nPosStride*I1]);
      Vec3 & tv2 = *((Vec3*)&pPos[nPosStride*I2]);

      if (Intersect::Line_Triangle( inLine, tv0, tv2, tv1, vOut ))// || Intersect::Line_Triangle( inLine, tv0, tv1, tv2, vOut ))
      {
        float fDistance = (hitInfo.inReferencePoint - vOut).GetLengthFast();

        if (fDistance < fBestDist)
        {
          bAnyHit = true;
          fBestDist = fDistance;
          vHitPos = vOut;
          tri[0] = tv0; tri[1] = tv1; tri[2] = tv2;
        }
      }
    }
	}

	if(hitInfo.nHitTriID == HIT_UNKNOWN)
	{			
		/*if(nInds < 64)
		{
			PodArray<CRenderChunk>&	Chunks = pRenderMesh->GetChunks();
			int nChunkCount = Chunks.Count();
			for(int nChunkId = 0; nChunkId < nChunkCount; nChunkId++)
			{
				CRenderChunk *pChunk = &Chunks[nChunkId];
				if(pChunk->m_nMatFlags & MTL_FLAG_NODRAW || !pChunk->pRE)
					continue;

				bool b2Sided = false;

				if (pMtl)
				{
					const SShaderItem &shaderItem = pMtl->GetShaderItem(pChunk->m_nMatID);
					if (hitInfo.bOnlyZWrite && !shaderItem.IsZWrite())
						continue;
					if (!shaderItem.m_pShader || shaderItem.m_pShader->GetFlags2() & EF2_NODRAW || shaderItem.m_pShader->GetFlags() & EF_DECAL)
						continue;
					if (shaderItem.m_pShader->GetCull() & eCULL_None)
						b2Sided = true;
					if(shaderItem.m_pShaderResources && shaderItem.m_pShaderResources->GetResFlags() & MTL_FLAG_2SIDED) 
						b2Sided = true;
				}

				int nLastIndexId = pChunk->nFirstIndexId + pChunk->nNumIndices;

				if(nLastIndexId-1 >= nInds)
				{
					Error("%s (%s): invalid mesh chunk", __FUNCTION__, pRenderMesh->GetSourceName());
					return 0;
				}

				for (int i = pChunk->nFirstIndexId; i < nLastIndexId; i+=3)
				{
					int I0 = pInds[i+0];
					int I1 = pInds[i+1];
					int I2 = pInds[i+2];

					// get tri vertices
					Vec3 & tv0 = *((Vec3*)&pPos[nPosStride*I0]);
					Vec3 & tv1 = *((Vec3*)&pPos[nPosStride*I1]);
					Vec3 & tv2 = *((Vec3*)&pPos[nPosStride*I2]);

					if (Intersect::Line_Triangle( inLine, tv0, tv2, tv1, vOut ))// || Intersect::Line_Triangle( inLine, tv0, tv1, tv2, vOut ))
					{
						float fDistance = (hitInfo.inReferencePoint - vOut).GetLengthFast();

						if (fDistance < fBestDist)
						{
							bAnyHit = true;
							fBestDist = fDistance;
							vHitPos = vOut;
							tri[0] = tv0; tri[1] = tv1; tri[2] = tv2;
							hitInfo.nHitMatID = pChunk->m_nMatID;
							hitInfo.nHitTriID = i;
						}
					}
				}
			}
		}
		else */
	
#if !defined(__SPU__) //for PS3 and so SPUs, the GetTrisForPosition always returns NULL
		if(const PodArray<std::pair<int,int> > * pTris = rIntersectionRMData.pRenderMesh->GetTrisForPosition(inRay.origin + inRay.direction*0.5f, pMtl))
		{
			for(int nId = 0; nId<pTris->Count(); ++nId)
			{
				std::pair<int,int> & t = pTris->GetAt(nId);

        if(t.first+2 >= nInds)
          return false;

				int I0 = pInds[t.first+0];
				int I1 = pInds[t.first+1];
				int I2 = pInds[t.first+2];

        if(I0>=nVerts || I1>=nVerts || I2>=nVerts)
          return false;

				// get tri vertices
				Vec3 & tv0 = *((Vec3*)&pPos[nPosStride*I0]);
				Vec3 & tv1 = *((Vec3*)&pPos[nPosStride*I1]);
				Vec3 & tv2 = *((Vec3*)&pPos[nPosStride*I2]);

				if (Intersect::Line_Triangle( inLine, tv0, tv2, tv1, vOut ))// || Intersect::Line_Triangle( inLine, tv0, tv1, tv2, vOut ))
				{
					float fDistance = (hitInfo.inReferencePoint - vOut).GetLengthFast();

					if (fDistance < fBestDist)
					{
						bAnyHit = true;
						fBestDist = fDistance;
						vHitPos = vOut;
						tri[0] = tv0; tri[1] = tv1; tri[2] = tv2;
						hitInfo.nHitMatID = t.second;
						hitInfo.nHitTriID = t.first;
					}
				}
			}
		}
#endif
	}

	if (bAnyHit)
	{ 
		hitInfo.pRenderMesh = rIntersectionRMData.pRenderMesh;

		// return closest to the shooter
		hitInfo.fDistance = fBestDist;
		hitInfo.vHitNormal = (tri[1]-tri[0]).Cross(tri[2]-tri[0]).GetNormalized();
		hitInfo.vHitPos = vHitPos;
		hitInfo.nHitSurfaceID = 0; 

		if (pMtl)
		{
			pMtl = pMtl->GetSafeSubMtl(hitInfo.nHitMatID);
			if (pMtl)
				hitInfo.nHitSurfaceID = pMtl->GetSurfaceTypeId();
		}

		if(hitInfo.bGetVertColorAndTC && hitInfo.nHitTriID>=0)
		{
			int I0 = pInds[hitInfo.nHitTriID+0];
			int I1 = pInds[hitInfo.nHitTriID+1];
			int I2 = pInds[hitInfo.nHitTriID+2];

			// get tri vertices
			Vec3 & tv0 = *((Vec3*)&pPos[nPosStride*I0]);
			Vec3 & tv1 = *((Vec3*)&pPos[nPosStride*I1]);
			Vec3 & tv2 = *((Vec3*)&pPos[nPosStride*I2]);

			float u=0, v=0, w=0;
			if(GetBarycentricCoordinates(vHitPos-tv0, tv1-tv0, tv2-tv0, u, v, w, 16.0f))
			{
				float arrVertWeight[3] = { max(0.f,w), max(0.f,v), max(0.f,u) };
				float fDiv = 1.f/(arrVertWeight[0]+arrVertWeight[1]+arrVertWeight[2]);
				arrVertWeight[0]*=fDiv;
				arrVertWeight[1]*=fDiv;
				arrVertWeight[2]*=fDiv;

				Vec2 tc0 = ((Vec2f16*)&pUV[nUVStride*I0])->ToVec2();
				Vec2 tc1 = ((Vec2f16*)&pUV[nUVStride*I1])->ToVec2();
				Vec2 tc2 = ((Vec2f16*)&pUV[nUVStride*I2])->ToVec2();

				hitInfo.vHitTC = tc0*arrVertWeight[0] + tc1*arrVertWeight[1] + tc2*arrVertWeight[2];

				Vec4 c0 = (*(ColorB*)&pCol[nColStride*I0]).toVec4();
				Vec4 c1 = (*(ColorB*)&pCol[nColStride*I1]).toVec4();
				Vec4 c2 = (*(ColorB*)&pCol[nColStride*I2]).toVec4();

				// get tangent basis
				int nTangStride= rIntersectionRMData.nTangStride;
				int nBNormStride=rIntersectionRMData.nBNormStride;
				byte * pTang = rIntersectionRMData.pTang;
				byte * pBNorm = rIntersectionRMData.pBNorm;
				
				Vec4 tangent[3];
				Vec4 binormal[3];
				int arrId[3] = {I0,I1,I2};
				for(int ii=0; ii<3; ii++)
				{
					Vec4sf & Tangent = *(Vec4sf*)&pTang[nTangStride*arrId[ii]];               
					Vec4sf & Binormal = *(Vec4sf*)&pBNorm[nBNormStride*arrId[ii]];
					tangent[ii]	= Vec4((Tangent.x), (Tangent.y), (Tangent.z), (Tangent.w));
					binormal[ii]	= Vec4((Binormal.x), (Binormal.y), (Binormal.z), (Binormal.w));
				}

				hitInfo.vHitTangent = (tangent[0]*arrVertWeight[0] + tangent[1]*arrVertWeight[1] + tangent[2]*arrVertWeight[2]) / 32767.0f;
				hitInfo.vHitBinormal = (binormal[0]*arrVertWeight[0] + binormal[1]*arrVertWeight[1] + binormal[2]*arrVertWeight[2]) / 32767.0f;

				hitInfo.vHitColor = (c0*arrVertWeight[0] + c1*arrVertWeight[1] + c2*arrVertWeight[2]) / 255.f;			
			}
		}
	}

  //CTimeValue t1 = gEnv->pTimer->GetAsyncTime();
  //CryLogAlways( "TestTime :%.2f", (t1-t0).GetMilliSeconds() );

  return bAnyHit;
}
